package com.xiaoyu.arrays;

/**
 * @program: DS_and_A
 * @description:
 * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点(i,ai) 。
 * 在坐标内画 n 条垂直线，垂直线 i的两个端点分别为(i,ai) 和 (i, 0) 。
 * 找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
 *
 * 说明：你不能倾斜容器。
 *
 * 输入：[1,8,6,2,5,4,8,3,7]
 * 输出：49
 * 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
 *
 * @author: YuWenYi
 * @create: 2021-05-31 08:49
 **/
public class MaxWaterArea_11 {

    //自己的思路,先移动左边,如果左边移动不了了,就再移动右边,直到两边都移动不了了,就退出循环
    //但是!!还是想简单了,无法解决1,3,2,5,25,24,5这种先减后加型的数列,所以算法错误!!
    public int maxArea(int[] height) {
        int n = height.length;
        int p1 = 0;
        int p2 = n - 1;
        int res = (p2 - p1) * Math.min(height[0],height[n-1]);
        int width;
        while (p1 != p2){
            width = p2 - p1;
            if (height[p1+1] > height[p1]){
                int temp = (p2-p1-1) * Math.min(height[p1+1], height[p2]);
                if (temp > res){
                    res = temp;
                }
                p1++;
            }else {
                if (height[p2-1] > height[p2]){
                    int temp = (p2-1-p1) * Math.min(height[p1], height[p2-1]);
                    if (temp > res){
                        res = temp;
                    }
                    p2--;
                }
            }
            if (width == (p2 - p1)){
                break;
            }
        }
        return res;
    }


    //转换思路,把每次移动不了p1再移动p2,改成-->看p1和p2位置谁的高度更低,就移动谁,这样修改后就是答案!!!!
    public int maxArea1(int[] height) {
        int n = height.length;
        int p1 = 0;
        int p2 = n - 1;
        int res = (p2 - p1) * Math.min(height[0],height[n-1]);
        while (p1 != p2){
            int temp = (p2-p1) * Math.min(height[p1], height[p2]);
            res = Math.max(temp,res);
            if (height[p1] < height[p2]){
                p1++;
            }else {
                p2--;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] height = {1,3,2,5,25,24,5};
        MaxWaterArea_11 maxWaterArea11 = new MaxWaterArea_11();
        System.out.println(maxWaterArea11.maxArea1(height));
    }
}
